C---------------------------------------------------------
C    TOOLPACK/1    Release: 1.1
C---------------------------------------------------------
C
C  ZBTADD - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  ADD AN ELEMENT TO THE BINARY TREE
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR 'NOERR'
C
      INTEGER FUNCTION ZBTADD(PLACE, VALUES, ARRAY)
 
      INTEGER PLACE, I, POINT, OFFSET, ROOM
      INTEGER ARRAY(*), VALUES(*)
 
C  CHECK LEGALITY OF REQUEST. MUST BE CURRENTLY AT A NODE THAT
C  HAS A FREE SLOT IN THE REQUESTED BRANCH POSITION.
      ZBTADD = -1
      IF(ARRAY(1) .NE. 98) RETURN
 
      IF(PLACE .EQ. 108) THEN
        IF(ARRAY(ARRAY(5)    ) .NE. 0) RETURN
        OFFSET = 0
      ELSE IF(PLACE .EQ. 114) THEN
        IF(ARRAY(ARRAY(5) + 1) .NE. 0) RETURN
        OFFSET = 1
      ELSE
        RETURN
      ENDIF
 
C  CHECK TO SEE IF THERE IS ENOUGH SPACE. NOTE THAT IF THE MAXIMUM
C  DEPTH OF THE TREE IS ABOUT TO BE INCREASED THEN AN ADJUSTMENT TO
C  THE CALCULATION IS MADE.
      ZBTADD = -100
      ROOM = (ARRAY(2) - 8 - ARRAY(7))
      IF(ARRAY(6) .EQ. ARRAY(7)) ROOM = ROOM - 1
      ROOM = ROOM / (ARRAY(3) + 2)
      IF(ARRAY(4) .EQ. ROOM) RETURN
 
      IF(ARRAY(6) .EQ. ARRAY(7)) ARRAY(7) = ARRAY(7) + 1
      POINT = 9 + (ARRAY(4) * (ARRAY(3) + 2))
 
C  SET UP THE NEW NODE AND LINK IT IN TO THE TREE.
      ARRAY(POINT)             = 0
      ARRAY(POINT + 1)         = 0
      ARRAY(ARRAY(5) + OFFSET) = POINT
 
      DO 10 I = 1, ARRAY(3)
        ARRAY(POINT + 1 + I) = VALUES(I)
   10 CONTINUE
 
C  INCREASE THE COUNT OF ENTRIES
      ARRAY(4) = ARRAY(4) + 1
      ZBTADD = -2
 
      RETURN
      END
C----------------------------------------------------------------------
C
C  ZBTINT - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  INITIALISE AN ARRAY AS A BINARY TREE
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' (THE SIZE OF THE ARRAY
C  OR SPECIFIED WIDTH IS WRONG) OR 'NOERR'. THERE IS
C  AN OVERHEAD OF 8 LOCATIONS RESERVED BY THE ROUTINES.
C  AN ADDITIONAL OVERHEAD OF 2 LOCATIONS PER TREE ENTRY IS USED TO
C  RETAIN THE POINTERS. A STACK IS HELD AT THE END OF THE ARRAY.
C
      INTEGER FUNCTION ZBTINT(ARRAY, SIZE, WIDTH, ROTVAL)
 
      INTEGER SIZE, WIDTH, I
      INTEGER ARRAY(*), ROTVAL(*)
 
      ZBTINT = -1
      IF(WIDTH .LE. 0)          RETURN
      IF(SIZE  .LT. WIDTH + 11) RETURN
 
C  IDENTIFY THE ARRAY AS A BINARY TREE
      ARRAY(1) = 98
C  THE SIZE OF THE ARRAY
      ARRAY(2) = SIZE
C  THE WIDTH OF EACH ELEMENT
      ARRAY(3) = WIDTH
C  THE NUMBER OF ENTRIES
      ARRAY(4) = 1
C  THE CURRENT NODE POINTER
      ARRAY(5) = 9
C  THE CURRENT LEVEL (1 = ROOT, 0 = ZBTNXT NOT CALLED YET)
      ARRAY(6) = 0
C  THE MAXIMUM SIZE OF STACK/DEPTH OF TREE
      ARRAY(7) = 1
C  THE CURRENT NUMBER OF STACK ENTRIES
      ARRAY(8) = 0
 
C  SET UP THE ROOT NODE
      ARRAY(9)  = 0
      ARRAY(10) = 0
      DO 10 I = 1, WIDTH
        ARRAY(10 + I) = ROTVAL(I)
   10 CONTINUE
 
      ZBTINT = -2
 
      RETURN
      END
C-----------------------------------------------------------
C
C  ZBTNXT - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  GO TO THE NEXT NODE OF THE TREE
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR THE FREE
C  SIBLING POINTER INFORMATION
C
      INTEGER FUNCTION ZBTNXT(VALUES, ARRAY)
 
      INTEGER I
      INTEGER ARRAY(*), VALUES(*)
 
C  CHECK LEGALITY OF REQUEST
      ZBTNXT = -1
      IF(ARRAY(1) .NE. 98) RETURN
 
C  IF THE TREE POINTER HAS JUST BEEN RESET THEN MOVE TO THE FIRST
C  POSITION, OTHERWISE SKIP DIRECT TO CHECKING THE RIGHT BRANCH.
      IF(ARRAY(6) .NE. 0) GO TO 40
      ARRAY(6) = 1
 
   30 CONTINUE
   10 CONTINUE
        IF(ARRAY(ARRAY(5)) .NE. 0) THEN
          ARRAY(ARRAY(2) - ARRAY(8)) = ARRAY(5)
          ARRAY(8) = ARRAY(8) + 1
          ARRAY(6) = ARRAY(6) + 1
          ARRAY(5) = ARRAY(ARRAY(5))
          GO TO 10
        ENDIF
      DO 20 I = 1, ARRAY(3)
        VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
   20 CONTINUE
      GO TO 100
 
   40 CONTINUE
 
C  NORMAL START OF PROCESSING. IF IT IS POSSIBLE TO TAKE A RIGHT BRANCH
C  THEN DO SO AND FIND ITS LEFT MOST DECSENDENT.
      IF(ARRAY(ARRAY(5) + 1) .NE. 0) THEN
        ARRAY(5) = ARRAY(ARRAY(5) + 1)
        ARRAY(6) = ARRAY(6) + 1
        GO TO 30
      ENDIF
 
C  IF THE STACK IS EMPTY THEN THIS IS THE END OF THE LINE
      IF(ARRAY(8) .EQ. 0) THEN
        ZBTNXT = -100
        RETURN
 
C  POP AN ELEMENT OFF THE STACK AND CONTINUE
      ELSE
        ARRAY(8) = ARRAY(8) - 1
        ARRAY(5) = ARRAY(ARRAY(2) - ARRAY(8))
        ARRAY(6) = ARRAY(6) - 1
        DO 50 I = 1, ARRAY(3)
          VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
   50   CONTINUE
        GO TO 100
 
      ENDIF
 
  100 CONTINUE
      ZBTNXT = -2
 
      RETURN
      END
C-----------------------------------------------------------------
C
C  ZBTRST - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  INITIALISE THE POINTER AND RECOVERY ORDER FOR THE BINARY TREE.
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
C
      INTEGER FUNCTION ZBTRST(ARRAY)
 
      INTEGER ARRAY(*)
 
      ZBTRST = -1
      IF(ARRAY(1) .NE. 98) RETURN
 
C  THE CURRENT NODE POINTER
      ARRAY(5) = 9
C  THE CURRENT LEVEL (0 = ROOT)
      ARRAY(6) = 0
C  THE STACK POINTER
      ARRAY(8) = 0
 
      ZBTRST = -2
 
      RETURN
      END
C--------------------------------------------------------------
C
C  ZBTTYP - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  RETURN INFORMATION ABOUT A BINARY TREE
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
C
      INTEGER FUNCTION ZBTTYP(ARRAY, WIDTH, ENTRYS, FREE)
 
      INTEGER ENTRYS, FREE, WIDTH
      INTEGER ARRAY(*)
 
      ZBTTYP = -1
      IF(ARRAY(1) .NE. 98) RETURN
 
C  THE WIDTH OF EACH ELEMENT
      WIDTH  = ARRAY(3)
C  THE NUMBER OF ENTRIES
      ENTRYS = ARRAY(4)
C  THE MAXIMUM NUMBER OF ENTRIES
      FREE = (ARRAY(2) - 8 - ARRAY(7)) / (ARRAY(3) + 2)
      FREE = FREE - ENTRYS
 
      ZBTTYP = -2
 
      RETURN
      END
C-----------------------------------------------------------
C
C  ZBTBRA - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  DIRECTED TREE TRAVERSAL
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR', 'EOF' OR THE FREE
C  SIBLING POINTER INFORMATION
C
      INTEGER FUNCTION ZBTBRA(DIRECT, VALUES, ARRAY)
 
      INTEGER  DIRECT, I, TEMP
      INTEGER  ARRAY(*), VALUES(*)
      INTEGER  ZBTRST
      EXTERNAL ZBTRST
 
C  CHECK LEGALITY OF REQUEST
      ZBTBRA = -1
      TEMP = ARRAY(5)
      IF(ZBTRST(ARRAY) .EQ. -1) RETURN
 
      IF(DIRECT .EQ. 108) THEN
        IF(ARRAY(TEMP) .EQ. 0) RETURN
        ARRAY(5) = ARRAY(TEMP)
 
      ELSE IF(DIRECT .EQ. 114) THEN
        IF(ARRAY(TEMP + 1) .EQ. 0) RETURN
        ARRAY(5) = ARRAY(TEMP + 1)
 
      ELSE
        ARRAY(5) = TEMP
        ZBTBRA = -1
 
      ENDIF
 
      DO 20 I = 1, ARRAY(3)
        VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
   20 CONTINUE
 
      IF(ARRAY(ARRAY(5)) .EQ. 0) THEN
        ZBTBRA = 108
        IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTBRA = 98
      ELSE
        ZBTBRA = 102
        IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTBRA = 114
      ENDIF
 
      RETURN
      END
C-----------------------------------------------------------------
C
C  ZBTTOP - 05 MAR 84
C           TIE LIBRARY
C           TABLES SUPPLEMENTARY LIBRARY
C
C  INITIALISE THE TREE FOR DIRECTED TRAVERSAL
C
C  THE VALUE OF THE FUNCTION IS EITHER 'ERR' OR 'NOERR'
C
      INTEGER FUNCTION ZBTTOP(VALUES, ARRAY)
 
      INTEGER  I
      INTEGER  ARRAY(*), VALUES(*)
      INTEGER  ZBTRST
      EXTERNAL ZBTRST
 
      ZBTTOP = -1
      IF(ZBTRST(ARRAY) .EQ. -1) RETURN
 
      DO 10 I = 1, ARRAY(3)
        VALUES(I) = ARRAY(ARRAY(5) + 1 + I)
   10 CONTINUE
 
      IF(ARRAY(ARRAY(5)) .EQ. 0) THEN
        ZBTTOP = 108
        IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTTOP = 98
      ELSE
        ZBTTOP = 102
        IF(ARRAY(ARRAY(5) + 1) .EQ. 0) ZBTTOP = 114
      ENDIF
 
      RETURN
      END
